package com.ieslab.backtracking;

/**
 * n皇后问题的非递归解法，可认为：<b>数组+循环控制+回溯</b>实现了任意n层嵌套循环的问题
 */
public class QueenProblemUnrecurision {
	private static int[] a = new int[20];
	private static int queenCount;

	public static void main(String[] args) {
		queenCount = 4;
		backdata(queenCount);
	}

	private static void backdata(int n) {
		int k = 1; // 第k个皇后
		a[1] = 0;
		while (k > 0) {
			a[k] = a[k] + 1;
			while (a[k] <= n && !check(k)) { // 为第k个皇后搜索位置
				a[k] = a[k] + 1;
			}
			if (a[k] <= n) {
				if (k == n) { // 找到一组解，到达叶子层节点
					output(n);
				} else { // 前k个皇后找到位置，继续为第k+1个皇后找位置
					k = k + 1;
					a[k] = 0; // 注意：下一个皇后一定从头开始搜索
				}
			} else {
				k = k - 1; // 回溯
			}
//			System.out.println("k=" + k); // 搜索完毕时，终止循环
			if (k == 0) {
				System.out.println("最终a的状态为");
				for (int i = 0; i != a.length; i++) {
					System.out.print(a[i]);
				}
			}
		}
	}

	/**
	 * 判断第k个皇后是否满足约束条件(与前k-1个元素逐个比较)
	 * 
	 * @param k
	 * @return
	 */
	private static boolean check(int k) {
		for (int i = 1; i < k; i++) {
			// 在同一列或在对角线(主、副对角线)上；相比判断不相等，更高效，因为不满足约束条件的多
			if (a[i] == a[k] || Math.abs(a[i] - a[k]) == Math.abs(i - k)) {
				return false;
			}
		}
		return true;
	}

	private static void output(int n) {
		for (int i = 1; i <= n; i++) {
			System.out.print(a[i]);
		}
		System.out.println();
	}
}
